package LinkedList;

import Utils.ListNode;

import java.util.List;

/**
 * 奇偶链表
 * 给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。
 * 请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。
 *
 * Lettcode 328: https://leetcode-cn.com/problems/odd-even-linked-list/
 */
public class oddEvenList {
    /**
     * 方法一： 创建一个链表，存储返回值的结果，通过两个指针对奇偶进行判断
     * 时间复杂度： O(n)  空间复杂度： O(n)
     * @param head
     * @return result head
     */
    public ListNode oddEvenList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode res = new ListNode(-1);
        ListNode temp;
        temp = res;
        ListNode odd = head;
        ListNode even = head.next;
        while (odd != null) {
            temp.next = new ListNode(odd.val);
            temp = temp.next;
            if (odd.next == null) {
                break;
            }
            odd = odd.next.next;
        }
        while (even != null) {
            temp.next = new ListNode(even.val);
            temp = temp.next;
            if (even.next == null) {
                break;
            }
            even = even.next.next;
        }
        temp.next = null;
        return res.next;
    }

    /**
     * 方法二：直接用两个ListNode把奇数节点和偶数节点分开，然后链接即可
     * 时间复杂度： O(n) 空间复杂度： O(1)
     * @param head
     * @return
     */
    public ListNode oddEvenListI(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while (even != null && even.next != null) {
            odd.next = odd.next.next;
            odd = odd.next;
            even.next = even.next.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}
